package recursive;

public class Binomial {
    //递归算法
    public long recursion(int k, int n) {
        if (k == 0 || k == n) {
            return 1;
        } else
            //如果第一个元素一定在结果中，那么就需要从剩下的n-1个元素中抓取k-1个元素，
            // 如果第一个元素不在结果中，就需要从剩下的n-1个元素中抓取k个元素
            return recursion(k, n - 1) + recursion(k - 1, n - 1);
    }

    // 备忘录方法
    public long memorandum(int k, int n) {
        long[][] binomial = new long[n + 1][k + 1];
        return getBinomial(binomial, k, n);
    }

    public long getBinomial(long[][] binomial, int k, int n) {
        long value;
        if (k == 0 || k == n) {
            value = 1;
        } else if (binomial[n][k] != 0) {//判断是否已经运算过。
            value = binomial[n][k];
        } else {
            //同递归
            value = getBinomial(binomial, k, n - 1) + getBinomial(binomial, k - 1, n - 1);
        }

        binomial[n][k] = value;

        return value;
    }

    //迭代算法
    /*
               * 1
               * 11
               * 121
               * 1331
               * 14641
               * .......
               * */

    public long iteration(int k, int n) {
        int[][] binomial = new int[n + 1][n + 1];
        binomial[0][1] = 1;
        binomial[1][1] = 1;

        //初始化杨辉三角
        for (int i = 2; i <= n; i++) {
            binomial[0][i] = 1;
            binomial[i][i] = 1;
        }

        //Cn k = Cn-1 k-1 + Cn-1 k
        for (int j = 2; j <= n; j++) {
            for (int i = 1; i < j; i++) {
                binomial[i][j] = binomial[i - 1][j - 1] + binomial[i][j - 1];
            }
        }

        return binomial[k][n];
    }
}
